The present invention relates to the field of graph rendering and, more particularly, to optimizing edge crossing computations when creating a drawing of a directed graph having a minimum number of edge crossings.
One objective of software that draws directed graphs or digraphs is to produce a graph that is easy to comprehend and that is aesthetically pleasing. One factor that influences the clarity of a directed graph is a number of crossings of edges between nodes, where fewer crossings generally results in superior clarity. Minimizing a number of crossings of edges, however, is a difficult mathematical problem, which is non-deterministic (e.g., NP-hard) in nature. Solutions (e.g., Sugiyama algorithm) to minimize crossings of edges use heuristic methods to refine graph structures, which are generally easy to compute and result in graphs with acceptably low numbers of edge crossings. One of the time consuming aspects of this type of approach is to determine the total number of edge crossings for the entire graph, which is repeated for a large number of possible graphs, referred to as candidate graphs.
The Sugiyama algorithm initially changes a graph into a “proper” hierarchical graph that has no cycles, and only has edges between adjacent levels. That is, cycles are removed from the graph by reversing and marking edges that cause cycles and inserting dummy nodes to ensure that no edges span more than one node. Each pair of levels in the layered graph is taken sequentially and a connection matrix is calculated, with which a number of crossings can be computed. A count for each pair of levels is accumulated and a total of crossing counts for each level pair is taken as the total number of edge crossings for the graph.
The Sugiyama algorithm includes steps that perform sweeps down and up the layered graph, which render nodes at each level in an attempt to obtain a better solution with a reduced number of crossings. If the number of edge crossings for a candidate graph is lower than a current best graph with the lowest number of crossings, then the candidate graph becomes the current best graph. When optimizations are finished, a current best graph is used as the graph with a minimized number of crossings.
Currently used algorithms calculate a number of crossings for an entire graph before the comparison between the candidate and current best graph is evaluated. This can be inefficient, as calculations for the total number of crossings of a candidate graph are performed, even after it is mathematically apparent that the candidate graph will include more crossings than the current best graph.